
#coding:utf-8
from __future__ import division
import numpy as np
def Simplex(A,b,c,B_I):
    number = len(np.array(A).T)
    m = len(A)
    while 1:
        if min(c) >= 0:
            x = z
            return x
            break
        delta = []
        Index_Min = c.index(min(c))
        arr = []
        for i in range(m):
            if A[i][Index_Min]>0:
                delta.append(float(b[i])/A[i][Index_Min])
                arr.append(i)
            else:
                delta.append(10e8)
        l = delta.index(min(delta))
        if delta[l]>10e7:
            return "unbounded"
        Pivot(B_I, A, b, c, Index_Min, l, arr)

def Pivot(B_I, A, b, c, Index_Min, l, arr):
    global z
    for i in range(len(A)):
        if i != l and i in arr:
            coefficient = A[i][Index_Min] / A[l][Index_Min]
            b[i] = b[i] - b[l] * coefficient
            for j in range(len(np.array(A).T)):
                A[i][j] = A[i][j] - coefficient * A[l][j]
    another_co = c[Index_Min] / A[l][Index_Min]
    for j in range(len(c)):
        c[j] = c[j] - another_co * A[l][j]
    z = z + abs(another_co) * b[l]

if __name__ == "__main__" :
    A = [[1, 1, 1, 1, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [0, 3, 1, 0, 0, 0, 1]]
    b = [4, 2, 3, 6]
    c = [-1, -14, -6, 0, 0, 0, 0]
    z = 0
    B_I = []
    print Simplex(A, b, c, B_I)
    print b
    print
    print c
    row = 3
    B = []
    for j in range(row):
        B1 = []
        for i in range(len(A)):

            B1.append(A[i][j])
        B.append(B1)
    B1 = []
    B2 = []
    for i in range(row):
        if B[i].count(0) == 3:
            B1.append(i)
            for j in range(len(A)):
                if B[i][j] != 0 :
                    B2.append(j)
    print B1
    print B2
    for i in range(len(B1)):
        num = b[B2[i]] / B[B1[i]][B2[i]]
        print "第%d个变量的值是%f" %(B1[i] + 1, num)



